package searchRange34;

public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        //先用二分法找到左面的值，之后再循环数组找到右面的值。
        int n = nums.length;
        int left = 0;
        int right = n;

        //先找左面的目标值

        while (left<right){
            int mid = (left + right) / 2;
            if(nums[mid] > target){
                //左边
                right  = mid-1;
            }else if(nums[mid] < target){
                //右边
                left = mid +1;
            }else {
                //相等--目的事尽量向左压缩。看左侧是否有目标相同的值
                right = mid;
            }

        }
        //判断不满足条件，n为0.或者左侧坐标就是n。或者上边找出的left所在位置不是目标值
        if (n == 0 || left == n || nums[left] != target) return new int[]{-1, -1};
        for (int i = left; i < n; i++) {
            if (nums[left] != nums[i]) break;
            right = i;
        }
        return new int[]{left, right};

    }

    public static void main(String[] args) {
        int[] a = {3, 4, 5, 6, 7, 8, 9, 9, 10};
        SearchRange searchRange = new SearchRange();
        for (int i : searchRange.searchRange(a, 9)) {
            System.out.println(i);
        }
    }
}
